package com.future;

/**
 * Description:
 * https://leetcode-cn.com/problems/target-sum/
 *
 * @Author: future
 * @Date:2022/2/28:21:47
 */
public class Solution_findTargetSumWays_494 {


    public static void main(String[] args) {
        int[] nums = {1, 2, 1};
        int target = 0;
        System.out.println(findTargetSumWays(nums, target));
    }

    public static int findTargetSumWays(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        return process(nums, 0, target);
    }

    private static int process(int[] nums, int curIndex, int rest) {
        if (curIndex == nums.length) {
            return rest == 0 ? 1 : 0;
        }
        return process(nums, curIndex + 1, rest - nums[curIndex]) + process(nums, curIndex + 1, rest + nums[curIndex]);
    }
}
